﻿namespace 数独
{
    public class Solution
    {
        /**
         * 行
         */
        static readonly int ROW = 9;
        /**
         * 列
         */
        static readonly int COL = 9;

        /**
         * 第i行是否填充了value
         */
        readonly bool[,] row = new bool[ROW, COL];

        /**
         * 第i列是否填充了value
         */
        readonly bool[,] col = new bool[ROW, COL];

        /**
         * 第i个小九宫是否填充了value
         */
        readonly bool[,] mid = new bool[ROW, COL];

        /**
         * 数独
         */
        public char[,] board;
        /**
         * 是否已经得出答案
         */
        bool solve = false;

        /**
         * 求解数独
         * @param board 数独
         */
        public void SolveSudoku(char[,] board)
        {

            //初始化三个布尔数组
            for (int i = 0; i < ROW; i++)
            {
                for (int j = 0; j < COL; j++)
                {
                    if (board[i, j] == '.')
                    {
                        continue;
                    }
                    else
                    {
                        row[i, board[i, j] - '0' - 1] = true;
                        col[j, board[i, j] - '0' - 1] = true;
                        mid[i / 3 * 3 + j / 3, board[i, j] - '0' - 1] = true;
                    }
                }
            }

            this.board = board;

            Dfs(0, 0);
        }

        /**
         * 深度优先
         * @param board
         * @param i
         * @param j
         */
        public void Dfs(int i, int j)
        {
            //已经解决则不再计算
            if (solve)
            {
                return;
            }

            //已经解决的条件
            if (i >= ROW || j >= COL)
            {
                solve = true;
                return;
            }

            //不是空格则无法填数
            if (board[i, j] != '.')
            {
                if (j == COL - 1)
                {
                    Dfs(i + 1, 0);
                }
                else
                {
                    Dfs(i, j + 1);
                }
                return;
            }

            //尝试填入1~9，只有没出现过的才能填入，且填入后立即更新已填的布尔数组，事后变回原样
            for (int number = 1; number <= 9; number++)
            {
                //它是不合法的就跳过
                if (row[i, number - 1] || col[j, number - 1] || mid[i / 3 * 3 + j / 3, number - 1])
                {
                    continue;
                    //否则尝试填入
                }
                else
                {
                    //尝试填入
                    board[i, j] = (char)(number + 48);
                    //更新已填布尔数组
                    row[i, number - 1] = true;
                    col[j, number - 1] = true;
                    mid[i / 3 * 3 + j / 3, number - 1] = true;

                    //向下一个元素出发
                    //行末处，跳到下一行
                    if (j == COL - 1)
                    {
                        Dfs(i + 1, 0);
                        //未到行末，跳到此行下一个元素
                    }
                    else
                    {
                        Dfs(i, j + 1);
                    }

                    //尝试结束，若没有出结果则重置原样
                    if (solve)
                    {
                        return;
                    }
                    else
                    {
                        board[i, j] = '.';
                        row[i, number - 1] = false;
                        col[j, number - 1] = false;
                        mid[i / 3 * 3 + j / 3, number - 1] = false;
                    }

                }

            }
        }
    }
}